package com.astar {

	/**
	 * 寻路主要算法类
	 * */
	public class AStar {
		//开放列表或者叫待考察列表
		private var _openAry:Array;
		//关闭列表或者叫已考察列表
		private var _closeAry:Array;
		//网格实例
		private var _grid:Grid;
		//开始节点
		private var _startNode:Node;
		//终点节点
		private var _endNode:Node;
		//找到的路径数组
		private var _path:Array;
		//H值的估价方法，这里用的是几何估价法
		private var _heuristic:Function = euclidian;
		//走直线的代价，一般为了方便计算都是用10
		private var _straightCost:int = 10;
		//走斜线的代价，一般为了方便计算都是用14
		private var _diagCost:int = 14;

		public function AStar() {
		}

		/**寻找路径，将包含所有节点信息的grid传进来，返回是否找到路径*/
		public function findPath(grid:Grid):Boolean {
			//一系列的初始化
			_grid = grid;
			_openAry = new Array();
			_closeAry = new Array();
			_startNode = _grid.startNode;
			_endNode = _grid.endNode;
			_startNode.g = 0;
			//获取开始节点到终点节点的H值
			_startNode.h = _heuristic(_startNode);
			_startNode.f = _startNode.g + _startNode.h;
			//开始寻路
			return search();
		}

		/**返回是否找到路径*/
		public function search():Boolean {
			//将起点设为当前节点
			var currentNode:Node = _startNode;
			//当起点和终点不是同一个点才会进入
			while (currentNode != _endNode) {
				/**计算起点周围八个方向的X、Y的范围（包括起点在内），
				 就是即将要加入计算的点，不明白请看图1*/
				var startX:int = Math.max(0, currentNode.x - 1);
				var endX:int = Math.min(_grid.numCol - 1, currentNode.x + 1);
				var startY:int = Math.max(0, currentNode.y - 1);
				var endY:int = Math.min(_grid.numRow - 1, currentNode.y + 1);
				for (var i:int = startX; i <= endX; i++) {
					for (var j:int = startY; j <= endY; j++) {
						var testNode:Node = _grid.getNode(i, j);
						/**如果这个节点是当前节点、不能通过的点、且排除水平和垂直方向
						 都是障碍物节点时能从斜角位置传过的特殊情况，
						 不明白请看图2*/
						if (testNode == currentNode || !testNode.walkable || !_grid.getNode(currentNode.x, testNode.y).walkable || !_grid.getNode(testNode.x, currentNode.y).walkable) {
							continue;
						}
						var cost:int = _straightCost;
						//如果当前点和测试点的x、y不相等的话，那么肯定走的不是横向或者纵向，而是斜线
						if (!((currentNode.x == testNode.x) || (currentNode.y == testNode.y))) {
							//所以改变cost代价
							cost = _diagCost;
						}
						//计算G值 = 当前点的G值 + 走一格的代价值 * 代价因子；
						var g:int = currentNode.g + cost * testNode.costMultiplier;
						//传入测试点估计H值
						var h:int = _heuristic(testNode);
						var f:int = g + h;
						//如果测试点在考察列表或者已考察列表中
						if (isOpenAry(testNode) || isCloseAry(testNode)) {
							//如果本次计算的F值更小，则以本次的F值为准
							if (f < testNode.f) {
								testNode.f = f;
								testNode.g = g;
								testNode.h = h;
								//重新指定该测试点为本轮计算中心点
								testNode.parent = currentNode;
							}
						} else  /**如果不在待考察列表和已考察列表中，
								则除了更新代价以及设置父节点外，
								还 要将该测试点加入待考察数组*/{
							testNode.f = f;
							testNode.g = g;
							testNode.h = h;
							testNode.parent = currentNode;
							_openAry.push(testNode);
						}
					}
				}
				//把经过这次处理的中心点加入到已考察列表中
				_closeAry.push(currentNode);
				//如果待考察列表的长度为0，则没找到路径
				if (_openAry.length == 0) {
					trace("no path");
					return false;
				}
				//将待考察列表中的值按F值从小到大排序
				_openAry.sortOn("f", Array.NUMERIC);
				/**从待考察列表中取出到终点所需代价最小的节点，重新赋值给当前节点，
				 做为下次的中心点，不断循环，直到当前点和终点节点是同一个节点时，
				 说明已经找到路径了*/
				currentNode = _openAry.shift() as Node;
			}
			//找到路径后开始构建路径数组
			buildPath();
			return true;
		}

		/**返回找到的路径数组*/
		public function get path():Array {
			return _path;
		}

		/**判断该节点是否在已考察列表中，默认返回false*/
		private function isCloseAry(node:Node):Boolean {
			for (var i:int = 0; i < _closeAry.length; i++) {
				if (_closeAry[i] == node) {
					return true;
				}
			}
			return false;
		}

		/**判断该节点是否在待考察列表中，默认返回false*/
		private function isOpenAry(node:Node):Boolean {
			for (var i:int = 0; i < _openAry.length; i++) {
				if (_openAry[i] == node) {
					return true;
				}
			}
			return false;
		}

		/**构建路径*/
		private function buildPath():void {
			_path = new Array();
			//终点节点
			var node:Node = _endNode;
			//在路径数组后push入终点节点
			_path.push(node);
			//当终点节点不等于开始节点时
			while (node != _startNode) {
				//不断地往回寻父节点，直到找到开始节点为止
				node = node.parent;
				//在路径数组头加入该节点，最终形成一个从起点节点到终点节点的一条路径数组
				_path.unshift(node);
			}
		}

		/**几何估价法，返回该节点的值*/
		private function euclidian(node:Node):int {
			//传入的节点 - 终点节点 的平方再开方，简单点就是勾股定理A²+B²=C²
			var dx:int = node.x - _endNode.x;
			var dy:int = node.y - _endNode.y;
			return Math.sqrt(dx * dx + dy * dy) * _straightCost;
		}
	}
}
